package ThirdWeek;

public class Saturday {
    //69、x的算数平方根
    public int mySqrt(int x) {
        //根据这个暴力解法可得，会分为两段，其一为小于等于x，其二为大于 x，在i这个平方后
        //可以根据二分查找
        if (x < 1) return 0;
        long left = 0,right = x;
        while(left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return (int)left;
    }

    public int mySqrt1(int x) {
        //暴力解法
        long i = 0;
        for (i = 0;i <= x;i++) {
            if (i * i == x) return (int)i;
            if (i * i > x) return (int)(i - 1);
        }
        return -1;
    }

    //34、在排序数组中查找元素的第一个和最后一个位置
    // 这里使用的是 二分查找 的通用使用方法
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        //处理一下边界的情况:
        if (nums.length == 0) {
            return ret;
        }

        int left = 0,right = nums.length - 1;
        //求其中的左端点
        while (left < right) {
            //这里不能是 left == right 的循环条件，因为会出现死循环，并且当这个条件的时候，我们如果存在结果就已经出现了在 left == right 这里
            int mid = left + (right - left) / 2;
            //这里不能是 mid = left + (right - left + 1) / 2;
            //因为当只有 2个数据的时候，mid就会在right这个位置，就会出现死循环了
            if (nums[mid] < target) {
                //这里是不存在正确结果的区间
                left = mid + 1;
            }else {
                right = mid;
            }
        }

        //出循环是因为left == right，这里判断这里是不是 我们需要的值，如果不是就返回ret
        if (nums[left] != target) {
            return ret;
        }else {
            ret[0] = left;
        }

        //求其中的右端点
        left = 0;
        right = nums.length - 1;
        while(left < right) {
            //这里的求 mid 的代码就会出现改变，如果还是上面的代码的话，mid就会在left这个位置上面，会出现死循环
            int mid = left + (right - left + 1) / 2;

            if (nums[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        //当代码执行到这里的时候呢，我们的数组区间里面就是存在 target这个要找的数据了，所以这里一定是找到了，直接赋值
        ret[1] = left;

        return ret;
    }
}
